Alkmini Sgouritsa

Personal Info

I am an Assistant Professor at the Athens University of Economics and Business (AUEB), Department of Informatics. I am further a Lead Researcher at Archimedes Unit of the Athena Research Center.

Previously, I was an Assistant Professor at the University of Liverpool, Department of Computer Science. During 2022, I was a Visiting Researcher at Google Research, CA, USA.

During the academic year 2018-2019 I was a PostDoctoral Research at the Max-Planck Institute for Informatics, in Algorithms and Complexity Department.

I completed my PhD in 2017 under the supervision of George Christodoulou at the University of Liverpool, Department of Computer Science. My PhD thesis on Algorithms for Game-Theoretic Environment was the highly-commended runner up for the prestigious British Computer Society (BCS) Distinguished Dissertation award in 2018. It can be found here. 

In parallel, in 2016, I worked as a Lecturer at the University of Liverpool for the MSc module “Algorithmic Game Theory”. 

I hold a master degree in Computer Science (with specialisation in Theoretical Computer Science) from the University of Edinburgh. My MSc thesis on Online Profit-Maximising Sampling Auctions For Digital Goods can be found here. I obtained my Diploma (MSc & BSc) from the School of Electrical and Computer Engineering National Technical University of Athens.

Here is my cv, my dblp page and my google scholar page.

Research Interest

Algorithmic Game Theory, Routing, Online Algorithms, Learning, Fair Division

Selected Scientific Work

• ML predictions in decentralised multi-agent systems

Recently, the leverage of ML predictions has been adapted in multi-agent systems. Our work in the following paper is one of the first in this area. While other works focus on centralised mechanisms, we are the first to design decentralised protocols under this learning-augmented framework with improved price of anarchy bounds. We do this for two classic decentralised resource allocation problems: scheduling games and network games.

Improved Price of Anarchy via Predictions

V. Gkatzelis, K. Kollias, A. Sgouritsa, X. Tan

23rd ACM Conference on Economics and Computations (EC) 2022.

Improving the Price of Anarchy via Predictions in Parallel-Link Networks

G. Christodoulou, V. Christoforidis, A. Sgouritsa, I. Vlachos

35th ACM Web Conference (WWW) 2026.

We further study the learning-augmented framework in mechanism design. In the following paper we consider several well-studied mechanism design paradigms, where the mechanisms os enhanced with an output recommendation.  We devise new mechanisms, but also provide refined analysis for existing ones, using as a metric the quality of recommendation. We complement our positive results, by exploring the limitations of known classes of strategyproof mechanisms that can be devised using output recommendation.

Mechanism design augmented with output advice 

G. Christodoulou, A. Sgouritsa, I. Vlachos

38th Annual Conference on Neural Information Processing Systems (NeurIPS-spotlight) 2024.

• Resource Aware Cost-Sharing Rules

Agents want to connect their origin and destination on a network and need to share the occurred cost on the edges that are used. How to share those costs affect the choices of the agents and therefore the equilibria. Prior to our work, two models had been considered with respect to the information that the designer of the cost-sharing rule has: he either has full information of the network and demand or is oblivious of both of them. Our work is the first to consider the more realistic scenario where the designer of the cost-sharing rule knows only the network but not the demand. In the following works, we show interesting separations from the other two models. 

Designing Networks with Good Equilibria under Uncertainty

G. Christodoulou, A. Sgouritsa, 

27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016, 

SIAM Journal on Computing (SICOMP) 2019.

Cost-Sharing Methods for Scheduling Games under Uncertainty

G. Christodoulou, V. Gkatzelis, A. Sgouritsa

18th ACM Conference on Economics and Computations (EC) 2017,

Operations Research (OR) 2024.

Resource-Aware Protocols for Network Cost-Sharing Games

G. Christodoulou, V. Gkatzelis, M. Latifian, A. Sgouritsa

21st ACM Conference on Economics and Computations (EC) 2020.

• Fair Division of Indivisible Goods

Arguably, one of the most important open problems in fair division of indivisible goods is the existence of EFX allocation; an allocation satisfies EFX, if no agent envies anybody else after the removal of any good from the latter's set. The state of the art is very poor: an EFX allocation exists a) when all agents have the same valuation function over the sets of goods, b) when there are only two agents, and c) when there are only three agents with additive valuations. Two main relaxations have also been studied: approximate-EFX and EFX with charity (i.e., some goods remain unallocated). 

Our following work lies on the first relaxation where we provide an improved approximation of EFX for several cases, tackling the problem by pushing from several different directions.

Pushing the Frontier on Approximate EFX Allocations

G. Amanatidis, A. Filos-Ratsikas, A. Sgouritsa

25th ACM Conference on Economics and Computations (EC) 2024.

We also had an important contribution regarding the second relaxation in the following work, where we provide an allocation with charity with the main property to be that nobody envies the charity. In other words, we provide an EFX allocation in the case that there exists a "dummy" agent that has zero value for every set of goods. 

A Little Charity Guarantees Almost Envy-Freeness

B.R. Chaudhury, K. Telikepalli, K. Mehlhorn, A. Sgouritsa

31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2020, 

SIAM Journal on Computing (SICOMP) 2021.

We further show in the following work how to find an EFX allocation in polynomial time in a restricted setting represented by a graph structure  that indicates which agents are interested in which goods.

Fair Allocation in Graphs

G. Christodoulou, A. Fiat, E. Koutsoupias, A. Sgouritsa

24th ACM Conference on Economics and Computations (EC) 2023.

• Universal TSP on the Grid

A universal algorithm finds a solution  for the universe of input elements and whenever an actual input appears it quickly adjusts the universal solution to the input. In the universal TSP, a global ordering of all possible clients is decided beforehand and when a subset of them requests service, the tour follows this order. In the following work, we disprove an almost 30-year conjecture made by Bertsimas and Grigni 1989, by showing that there exists a universal ordering on the grid with sublogarithmic competitive ratio.

An Improved Upper Bound for the Universal TSP on the Grid 

G. Christodoulou, A. Sgouritsa

28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2017,

SIAM Journal on Computing (SICOMP) (to appear).

Publications

Here is the whole list of my publications.

Research Funded Projects

• Lead Researcher in the Archimedes Research Unit, Athena Research Center. Title of Research Proposal: "Design of Algorithms for Games and Learning". Research Area: Game Theory/ Optimization/ Multi- Agent Learning. Estimated duration: February 2023 - December 2027.

•  Principal Investigator for the project "Algorithm Design for Fair Division project" (ADFD), funded by the Hellenic Foundation for Research and Innovation (H.F.R.I) under the Call “Basic Research Financing (Horizontal support for all Sciences), National Recovery and Resilience Plan (Greece 2.0) - Subproject 1: Funding New Researchers”. Duration: March 2024 - December 2025. Webpage: https://adfd.aueb.gr/

• Member of the research team (January 2026 - June 2026) for the project EXIGENCE "Devise & explore a novel approach for energy consumption and carbon footprint reduction of ICT services in the era of next-generation mobile telecommunications (6G)" (funded by the European Commission), under the Principal Investigator Georgios Stamoulis. Duration: January 2024 - June 2026.

Supervised Students

Current PhD students:

• Minas Marios Sotiriou (main supervisor), Athens University of Economics and Business

• Ioannis Vlachos (main supervisor), Athens University of Economics and Business

• Vasileios Christoforidis (co-supervisor), Aristotle University of Thessaloniki 

Here is a list of all students I have supervised.  

Teaching

Algorithmic Game Theory (MSc) - Athens University of Economics and Business

Game Theory and Decision Making (BSc) - Athens University of Economics and Business

Data Structures (BSc) - Athens University of Economics and Business

Data Structures and Algorithms (BSc) - Athens University of Economics and Business

Previously

Algorithms (BSc) - Athens University of Economics and Business

Introduction to Computer Science (BSc) - Athens University of Economics and Business

Database and Information Systems (MSc) - University of Liverpool

Algorithmic Game Theory  (MSc) - University of Liverpool

Computational Game Theory and Mechanism Design (BSc) - University of Liverpool